﻿// 167. 木棒.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <map>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

using namespace std;

/*
https://www.acwing.com/problem/content/169/
乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 50 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序，帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。

输入格式
输入包含多组数据，每组数据包括两行。
第一行是一个不超过 64 的整数，表示砍断之后共有多少节木棍。
第二行是截断以后，所得到的各节木棍的长度。
在最后一组数据之后，是一个零。

输出格式
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围
数据保证每一节木棍的长度均不大于 50。

输入样例：
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0


9
44 36 7 3 21 28 41 40 14
117

10
35 26 28 12 34 27 29 36 42 37

102



13
35 14 8 30 14 28 8 23 22 49 13 29 7
14
31 20 48 38 33 8 35 44 30 37 14 2 9 29
0

140
126




输出样例：
6
5
*/

int n;
const int N = 70;
int arr[N];
int maxLen;
int total;
int item[N];
int itemIdx;

unordered_set<int > ss;

bool dfs(int x,int used,int target) {
	if (x == total/ target) {
		return true;
	}

	for (int i = used; i < n; i++) {
		if (arr[i] != -1 && arr[i]+item[x] < target) {
			if (ss.count(arr[i] + item[x]) != 0) continue;
			int back = arr[i]; item[x] += arr[i]; arr[i] = -1;
			unordered_set<int > cp = ss;
			bool ret = dfs(x, i + 1, target);
			ss = cp;
			if (ret == false) {
				ss.insert(item[x]);
			}
			arr[i] = back;  item[x] -= arr[i];
			if (ret == true) return true;
			if (0 == item[x] && ret == false) return false;
		}
		else if (arr[i] != -1 && arr[i] + item[x] == target) {
			int back = arr[i]; item[x] += arr[i]; arr[i] = -1;
			ss.clear();
			bool ret = dfs(x+1, 0, target);
			arr[i] = back;  item[x] -= arr[i];
			if (ret == true) return true;
			if (ret == false) return false;
		}
	}

	return false;
}


int main()
{
	while (cin >> n) {
		if (n == 0) break;
		maxLen = 0; itemIdx = 0; total = 0;
		memset(item,0,sizeof item);
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
			maxLen = max(maxLen, arr[i]);
			total += arr[i];
		}
		sort(arr, arr + n,greater<int>());

		for (int i = maxLen; i <= total; i++) {
			if (total% i != 0) continue;
			ss.clear();
			if (dfs(0,0,i)) {
				cout << i << endl;
				break;
			}
		}
	}

	return 0;
}

 